package leedcode_path.treeNoDE;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Predicate;

public class 二叉搜索树中的众数 {
    /*
    * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树*/

    List<Integer> num = new ArrayList<Integer>();
    int count=1;
    int maxcount=0;

    TreeNode pre=null;
    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] res=num.stream().mapToInt(x->x).toArray();
        return res;




    }
    public void dfs(TreeNode root){
        if (root==null) return;

        dfs(root.left);
        if (pre==null){
            count=1;
        }else if (pre.val==root.val){
            count++;
        }else {
            count=1;
        }
        pre=root;
        if (count==maxcount) num.add(root.val);
        if (count>maxcount){
            maxcount=count;
            num.clear();
            num.add(root.val);
        }
        dfs(root.right);


    }

    public static void main(String[] args) {
        二叉搜索树中的众数 a=new 二叉搜索树中的众数();
        TreeNode a1=new TreeNode(2);
        TreeNode a2=new TreeNode(2,a1,null);
        TreeNode a3=new TreeNode(1,null,a2);
        int[] mode = a.findMode(a3);
        for (int i :mode
             ) {
            System.out.println(i);
        }

    }
}
